//
//  YKGraph.h
//  ProjectM
//
//  Created by gaofeng on 2021/6/20.
//

#ifndef YKGraph_h
#define YKGraph_h

#include <stdio.h>
#define kMaxVertexNum 30 //最大顶点数
// ==图的邻接矩阵存储结构定义==
typedef char VertexType;
typedef int EdgeType;
typedef struct {
    VertexType Vex[kMaxVertexNum]; //点集
    EdgeType Edge[kMaxVertexNum][kMaxVertexNum]; // 边集
    int vexnum,arcnum; // 顶点数和弧边数
}MGraph;
// ==图的邻接表存储结构定义==
typedef struct ArcNode{ //边表结点
    VertexType  adjvex; // 该弧所指向的顶点的位置
    struct  ArcNode *next; //指向下一条弧的指针
    //InfoType info; // 网的边权值
}ArcNode;
ArcNode *initArcNode(int adj, ArcNode *next);
typedef struct VNode { // 顶点表结点
    VertexType data; // 顶点信息
    ArcNode *first; // 指向第一条依附该顶点的弧的指针
}VNode,AdjList[kMaxVertexNum];
typedef struct {//
    AdjList vertices; // 邻接表
    int vexnum,arcnum; // 图的顶点数和弧数
}ALGraph; // 以邻接表存储的图的类型
// ==图的十字表存储结构定义==
typedef struct ArcNodeG{  //边表结点
    int  tailvex,headvex; // 弧的头尾结点
    struct  ArcNodeG *hlink,*tlink; // 分别指向弧头相同和弧尾相同的结点
    //InfoType info; // 相关信息指针
}ArcNodeG;
typedef struct VNodeG { // 顶点表结点
    VertexType data; // 顶点信息
    ArcNodeG *firstin,*firstout; // 指向第一条入弧和出弧
}VNodeG;
typedef struct {
    VNodeG xlist[kMaxVertexNum]; // 邻接表
    int vexnum,arcnum; // 图的顶点数和弧数
}GLGraph;
// ==无向图的邻接多重表存储结构定义==
typedef struct ArcNodeA{ // 边表结点
    int mark; // 访问标志
    int ivex,jvex; // 分别指向该弧的两个结点
    struct ArcNodeA *ilink,*jlink; // 分别指向两个顶点的下一条边
    // InfoType info; // 相关信息指针
}ArcNodeA;
typedef struct VNodeA{ // 顶点表结点
    VertexType data; // 顶点信息
    ArcNodeA *firstedge; // 指向第一条依附该顶点的边
}VNodeA;
typedef struct {
    VNodeA adjmulist[kMaxVertexNum]; // 邻接表
    int vexnum,arcnum; // 图的顶点数和弧数
}AMLGraph;
MGraph *initSpaceMGraph(void);
/** 图的基本操作
 * Adjacent(G,x,y)          判断图G是否存在边<x,y>或(x,y)
 * Neighors(G,x)            列出图G中与结点x的邻接的边
 * InsertVertex(G,x)        从图G中插入顶点x
 * DeleteVertex(G,x)        从图G中删除x顶点
 * AddEdge(G,x,y)           添加边，不存在才添加
 * RemoveEdge(G,x,y)        若无向图存在(x,y)则删除该边
 * FirstNeighbor(G,x)       求图G中顶点x的第一个邻接点，有则返回无则-1
 * NextNeighbor(G,x,y)      返回除y之外顶点x的下一个邻接点的顶点号，如果是y是x的最后一个邻接点，则返回-1
 * GetEdgeValue(G,x,y)      获取图G中边的权值
 * SetEdgeValue(G,x,y,v)    设置图G边的权值
 */
/** 判断图G是否存在边<x,y>或(x,y)
 * int 0 边存在； 1 顶点错误，边不存在；2 顶点真确，边不存在；3；顶点不存在环
 */
int AdjacentMGraph(MGraph * G,VertexType x,VertexType y);
#endif /* YKGraph_h */
